package hot100;

import org.junit.Test;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class MaxPathSum {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private int val = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        findMaxPathSum(root);
        return this.val;
    }

    private int findMaxPathSum(TreeNode root) {
        if (root == null) return 0;
        int left = findMaxPathSum(root.left);//左子树中的最大路径和
        int right = findMaxPathSum(root.right);//右子树中的最大路径和
        int case1 = root.val + left + right;//最大值可能为左右子树最大路径和与当前节点值之和
        int case23 = root.val + Math.max(0,Math.max(left,right));//最大值为当前节点值+左/右子树最大路径和+当前节点祖先节点路径
        this.val = Math.max(this.val,Math.max(case1,case23));
        return case23;
    }

    @Test
    public void test() {
        List<String> strings = Arrays.asList("1", "2", "3");
        String collect = strings.stream().filter(s -> s.equals("4")).collect(Collectors.joining(","));
        if (collect == null) System.out.println("null");
        else System.out.println("empty string");
    }
}
